\documentclass[12pt,fleqn]{article}
\usepackage {psfig,epsfig} % para incluir figuras em PostScript
\usepackage{amsfonts,amsthm,amsopn,amssymb,latexsym}
\usepackage[brazil]{babel}
\usepackage[utf8]{inputenc}
\usepackage{graphicx}
\usepackage[T1]{fontenc}
\usepackage{geometry}
\usepackage[intlimits]{amsmath}
%alguns macros
\newcommand{\R}{\ensuremath{\mathbb{R}}}
\newcommand{\Rn}{{\ensuremath{\mathbb{R}}}^{n}}
\newcommand{\Rm}{{\ensuremath{\mathbb{R}}}^{m}}
\newcommand{\Rmn}{{\ensuremath{\mathbb{R}}}^{{m}\times{n}}}
\newcommand{\contcaption}[1]{\vspace*{-0.6\baselineskip}\begin{center}#1\end{center}\vspace*{-0.6\baselineskip}}
%=======================================================================
% Dimenses da pgina
\usepackage{a4}                       % tamanho da pgina
\setlength{\textwidth}{16.0cm}        % largura do texto
\setlength{\textheight}{9.0in}        % tamanho do texto (sem head, etc)
\renewcommand{\baselinestretch}{1.15} % espaamento entre linhas
\addtolength{\topmargin}{-1cm}        % espao entre o head e a margem
\setlength{\oddsidemargin}{-0.1cm}    % espao entre o texto e a margem
       
% Ser indulgente no preenchimento das linhas
\sloppy
 

\begin{document}

% Pginas iniciais
\include {capa}           % capa ilustrativa


\tableofcontents


% Numerao em romanos para pginas iniciais (sumrios, listas, etc)
%\pagenumbering {roman}
\pagestyle {plain}

\setcounter{page}{0} \pagenumbering{arabic}
  
\setlength{\parindent}{0in}  %espaco entre paragrafo e margem 
% Espaamento entre pargrafos
\parskip 5pt  

\newpage

%################################ SEÇÃO 1 ################################
\section{Introdução}


Algoritmos Genéticos (AG) são usados para encontrar boas soluções para
problemas NP-Completo e NP-Hard. Os algoritmos existentes para solucionar tais problemas possuem complexidades exponenciais. 
Algoritmos Genéticos é a técnica mais disseminadas entre os algoritmos evolucionários, eles permitem calcular soluções 
satisfatórias para os problemas em uma tempo aceitável, especialmente para dados
de entrada que possuem tamanhos grandes.

Em um Algoritmo Genético,  as soluções candidatas de um problema são modelados
como indivíduos (cromossomos) de uma população. A população é inicializada
aleatoriamente (ou por alguma estratégia, dependendo do problema). A cada
indivíduo é atribuído um valor de fitness, que representa a sua qualidade em
relação a uma solução.  Dessa forma, objetiva-se encontrar o indivíduo com melhor fitness. 
A população passa por um número determinado de evolução. Durante esse processo
de evolução a população sobre variações, devido a uma série de operadores
genéticos. Os operadores básicos são de avaliação (\textit{fitness}),
seleção, cruzamento e mutação. 

No contexto deste trabalho, os algoritmos genéticos serão utilizados para
solucionar problemas de otimização e aprendizado de máquina. Os problemas
tratados neste trabalho, de acordo com a especificação, compartilham
características similares quanto à utilização do AG.

Este relatório está organizado da seguinte maneira: Na seção 2 é descrito o
arcabouço do algoritmo genético que serve de base para implementação dos
algoritmos para solução do problemas especificados para este trabalho. Na seção
3 é tratado o problema do labirinto, caracterizado com um problema de
otimização. Na seção 4, toda a abordagem utilizada durante a modelagem e
experimentação do problema do Comitê de Classificadore é descrita. Por fim, são
dadas as conclusões sobre a experiência de implementação do trabalho prático 1.
\newpage


%################################ SEÇÃO 2 ################################
\section{Arcabouço do Algoritmo Genético}

Para auxiliar o processo de implementação foi criado um arcabouço, chamado
FRAGA (FRAmework for Genetic Algorithm), em linguagem C++ que consiste de uma
composição de classes com responsabilidades bem definidas (isto é, baixo
acoplamento e alta coesão), visando representar entidades (e.g., Indivíduo,
população) e efetuar operações (e.g., mutação, cruzamento) requeridas pela abstração do algoritmo genético. Este arcabouço fornece recursos e
determina o fluxo de controle de execução do algoritmo genético.

O processo de utilização do arcabouço consiste em duas
partes, como mostra a Figura 1. A primeira parte representa a etapa de
entendimento e modelagem do problema de acordo com a especificação do arcabouço. A segunda
parte representa o processo de abstração utilizado na construção do
arcabouço.

\begin{figure}[!htb]
	\centering
		\includegraphics[scale=0.5]{images/Framework_pp.png}
	\label{fig:frame1}
	\caption{Algoritmo utilizado na construção do Arcabouço.}
\end{figure}

Cada bloco da da parte 2 pode ser interpretado como um passo do algoritmo
genético. Como descrito a seguir:

\begin{enumerate}
	\item O processo inicia com uma população de N indivíduos (cromossomos) sendo
	gerada aleatoriamente. Vale ressaltar, que esse indivíduos são soluções
	candidatas para o problema;
	\item Calcula-se a \textit{fitness} de cada indivíduo da população;
	\item Em seguida, os seguintes passos são executados até N descendentes tenham
	sido criados para formar uma nova população:
	\begin{itemize}
	  \item Seleciona-se um par de pais da população atual. Os métodos aplicados
	  podem ser roleta, torneio ou \textit{ranking};
	  \item Realiza-se o cruzamento entre os dois pais selecionados;
	  \item Efetua-se a mutação dos descendentes de acordo com a probabilidade de
	  mutação, em seguida, o adiciona em uma nova população;
	\end{itemize}
	\item Troca-se a população atual pela nova população;
	\item Retoma-se o algoritmo a partir do passo 2;
\end{enumerate}

Basicamente, o algoritmo anterior foi mapeado na linguagem C++ em quatro
classes (ver Figura 2). Descritas como segue: \textbf{class Individual}: Esta
classe representa um indivíduo (solução candidata) da população. Na versão atual do
arcabouço, a representação do genótipo do indivíduo é binária. No entanto,
dependendo do problema, a conversão para decimal pode ser realizada por meio de
um mapeamento binário-decimal; \textbf{class GA}: Esta classe possui todas as
funções básicas para funcionamento do algoritmo genético. Nela existe uma estrutura,
chamada \textit{population}, que armazena todos os indivíduos da população.
Adicionalmente, existem as funções de seleção, cruzamento, mutação operando com
ou sem elitismo; \textbf{class Problem}: Esta classe representa o problema a ser
resolvido. Então, é esta classe que deve ser customizada de acordo com o
problema. Por padrão, inicialmente, ela possui a responsabilidade de efetuar a
tradução de genótipo para fenótipo e realizar o cálculo da \textit{fitness}.
Entretanto, dependendo da modelagem do problema, pode-se adicionar mais
responsabilidades a ela; \textbf{class Main}: Esta é a classe de inicialização
do algoritmo. Todos os parâmetros de configuração do GA devem ser repassados a esta
classe para que a função de chamada do problema (\textit{call\_problem})
inicialize e execute o fluxo de chamadas das funções do algoritmo genético.

\begin{figure}[!htb]
	\centering
		\includegraphics[scale=1.0]{images/Framework_GA_.png}
	\label{fig:pdsmodel}
	\caption{Diagrama de Classes Simplificado do Arcabouço FRAGA.}
\end{figure}

%inicia uma nova pgina
\clearpage

%################################ SEÇÃO 3 ################################
\section{Problema 1: Labirinto}
\label{sec:tab}


\subsection{Descrição}

Como comentado na seção 1, algoritmos genéticos podem ser utilizados para
resolver problemas de otimização. Nesse sentido, para este trabalho prático, o
problema de otimização a ser resolvido com o uso de algoritmo genético é:
encontrar o menor caminho válido possível entre a entrada e saída de um labirinto.

O labirinto utilizado neste trabalho tem a seguinte representação:
\[
  m_{i,j} = 
   \begin{cases}
    0 & \text{se } m_{i,j} = corredor \\
    1 & \text{se } m_{i,j} = parede \\
   \end{cases}
\]

Uma matriz M com dimensões m x n, onde cada posição é definida como a função
acima. Dessa forma, para solucionar este problema, dados um ponto de partida
S$_{i,j}$ e um de chegada E$_{i,j}$ (com 0 < 1, k < m e 0 < j, l < n), encontrar
o menor caminho de S$_{i,j}$ a E$_{i,j}$. Então um caminho é válido se inicia em
S$_{i,j}$ e termina em E$_{i,j}$.  

\begin{figure}[!htb]
	\centering
		\includegraphics[scale=0.5]{images/entrada_saida_lab.png}
	\label{fig:es_lab}
	\caption{Configurações de entrada e saída para o problema do labirinto.}
\end{figure}

A Figura 3 mostra como foi modelado a estrutura do labirinto para representar
parede e corredor. A Figura 3 (a) é a representação fornecida pela especificação
do trabalho. A Figura 3 (b) é a conversão da entrada original para uma
representação de 0s e 1s, como dito na equação acima. A Figura 3 (c) é a saída
do algoritmo após a definição do caminho. O caminho válido é denotado pelo
caminho formado pelo número 4, como mostra a Figura 3 (c). 


\subsection{Representação do Indivíduo}

Uma das tarefas mais importante na modelagem de um problema para ser solucionado
usando algoritmo genético é definir a representação do indivíduo. Pelo que foi
descrito anteriormente, partindo da posição inicial S$_{i,j}$ dada, um caminho
deve ser construído a partir de quatro movimentos básicos, definidos a seguir:
\begin{itemize}
  \item N: mover para a posição adjacente ao norte; 
  \item S: mover para a posição adjacente ao sul;
  \item L: mover para a posição adjacente ao leste;
  \item O: mover para a posição adjacente ao oeste;
\end{itemize}

Visto que a representação do indivíduo no arcabouço FRAGA deve ser em binária.
Um par de dois bits é suficiente para representar os quatro movimentos. Nesse
sentido, temos que: 00 = S, 01 = L, 10 = O, 11 = N. Na Tabela 1 é mostrada uma
sequência de transformação do genótipo (representação binária) em
fenótipo (orientações N, S, L, O) para um certo caminho.

\begin{table}[htb]
\begin{center}
		\begin{tabular}{|c|c|c|c|c|c|c|c|}\hline
		Genótipo: & 10 & 10 & 11 & 01 & 11 & 01 & 00 \\\hline
		Fenótipo: & O & O & N & L & N & L & S \\\hline
		\end{tabular}
\label{tab:Tabela1}
\caption{Representação do indivíduo para o problema do labirinto.}
\end{center}
\end{table}

\subsection{Função de Fitness}

O cálculo da fitness para o problema do labirinto considera dois fatores: a
distância euclidiana da posição atual até a saída e a quantidade de passos
realizados corretos, ou seja, sem colisão. Esses fatores são inversamente
proporcionais a fitness, ou seja, quanto maior, menor a fitness.


\subsection{Experimentos}

\begin{figure}[!htb]
	\centering
		\includegraphics[scale=0.7]{images/res1.png}
	\label{fig:es_lab}
	\caption{Evolução do GA para labirinto 1}
\end{figure}

\begin{figure}[!htb]
	\centering
		\includegraphics[scale=0.7]{images/res2.png}
	\label{fig:es_lab}
	\caption{Evolução do GA para labirinto 2}
\end{figure}

%\begin{figure}[!htb]
%	\centering
%		\includegraphics[scale=0.7]{images/res3.png}
%	\label{fig:es_lab}
%	\caption{Evolução do GA para labirinto 3}
%\end{figure}
\newpage
\newpage

%% ################################SEÇÃO 4################################
\section{Problema 2: Comitê de Classificadores}

\subsection{Descrição}

Como comentado na seção 1, algoritmos genéticos podem ser utilizados para
resolver problemas de aprendizado de máquina. Nesse sentido, para este trabalho
prático, o problema de aprendizado de máquina a ser resolvido com o uso de
algoritmo genético é: definir um comitê de classificadores, ou seja, determinar
como combinar as predições dos classificadores de forma a maximar a acurácia.

\[
  c_{map} = arg \max_{c} \sum_{i=1}^{k} p_{i,c}w_i
\]

Para este problema a predição final é uma combinação ponderada das predições dos
classificadores, como mostra a equação acima. Desse modo, temos que os arquivos
disponibilizados na especificação deste trabalho serão utilizados para treino e
teste, aplicando a equação acima, na qual p$_{i,j}$ é a predição de
um classificador \textit{i} (1 $\leq$ i $\leq$ k, onde k é o número de
classificadores) em relação à classe \textit{j} (1 $\leq$ j $\leq$ n, onde n é o
número de classes) e w$_i$ corresponde ao peso do classificador \textit{i}.

\subsection{Representação do Indivíduo}

Na etapa de modelagem do problema para resolução usando um algoritmo genético
foi decidido utilizar uma representação decimal. Como o arcabouço FRAGA permite
apenas que os genótipos sejam composição de bits (0 ou 1), então foi necessário
fazer um mapeamento para um fenótipo decimal, como mostrado na Tabela 2. Para
tanto, foi criada uma função de conversão de representação binária para decimal,
como será discutido mais a frente na seção 4.4.

\begin{table}[htb]
\begin{center}
		\begin{tabular}{|c|c|c|c|}\hline
		 & $w_1$ & $w_2$ & $w_3$ \\\hline
		Genótipo: & 0001111 & 0010111 & 0101011 \\\hline
		Fenótipo: & 15  & 23 & 42 \\\hline
		\end{tabular}
\label{tab:Tabela1}
\caption{Representação do peso de cada classificador por indivíduo.}
\end{center}
\end{table}

Esses valores de pesos são aplicados na equação c$_{map}$ para então podermos
calcular a acurácia do indivíduo (combinação de pesos, conseqüentemente,
possível solução) como será descrito na próxima seção.

\subsection{Função de Fitness}

A função \textit{fitness} para este problema será baseada na acurácia produzida
pela combinação ponderada das predições dos \textit{n} classificadores. A
acurácia (\textit{Overall Accuracy - OA}) pode ser obtida através da razão entre
os dados corretamente classificados e o número total de dados classificados.
Dessa forma a função \textit{fitness} deverá encontrar os melhores pesos para
que ao calcular OA esta seja máxima. 

\subsection{Experimentos}

O conjunto de dados utilizados para experimentção são referentes a dados do
YouTube (Mais detalhes sobre dados são fornecidos na especificação do
trabalho). Esse conjunto de dados é a composição de predições de três
classificadores. Nesse sentido, o objetivo é determinar a melhor combinação de
pesos na formação do comitê.

Para o processo de experimentação foi adotada a técnica de validação cruzada.
Dessa maneira, fizemos a partição dos dados em cinco partes iguais. Dessa forma,
são criadas cinco configurações, a cada configuração uma parte do conjunto se
torna dado de teste, enquanto as demais partes compõem os dados de
treinamento.

\begin{figure}[!htb]
	\centering
		\includegraphics[scale=1.0]{images/comite - conjunto 1.png}
	\label{fig:es_lab}
	\caption{Apllicação do Comitê de Classificadores para o Conjunto de Dados 1.}
\end{figure}


\begin{figure}[!htb]
	\centering
		\includegraphics[scale=1.0]{images/comite_conjunto 2.png}
	\label{fig:es_lab}
	\caption{Apllicação do Comitê de Classificadores para o Conjunto de Dados 2.}
\end{figure}




%################################ SEÇÃO 5 ################################
\section{Conclusão} 

Algoritmos Genéticos são usados para encontrar boas soluções para problemas
considerados difíceis. Tais problemas estão na maioria na classe de
problemas de otimização, onde os algoritmos existentes para solucioná-los
possuem complexidades de tempo exponencial. Neste trabalho foram considerados
dois problemas: um problema de otimização e um problema de aprendizado de
máquina. Por meio desses problemas, podemos observar as vantagens e desvantagens
dos AG. Detalhes importantes como a representação do indivíduo e o quanto a
função de fitness determina em busca de uma boa solução.





\end{document} %finaliza o documento

